// 冒泡排序
let A = [9, 7, 8, 5, 6, 1]
function swap(A, i, j) {
  let temp = A[i]
  A[i] = A[j]
  A[j] = temp
}
function maopao(A) {
  for (let i = 0; i < A.length - 1; i++) {
    for (let j = 0; j < A.length - 1 - i; j++) {
      if (A[j] > A[j + 1]) {
        swap(A, j, j + 1)
      }
    }
  }
}
// maopao(A)


// 插入排序
// 假设一个是已经排序好的数组 向这个数组插入一个新的数
function insertSort(arr) {
  for(let i = 1; i<arr.length; i++) {
    let j = i
    let temp = arr[i]
    while(j>0 && temp<arr[j-1]) {
      arr[j] = arr[j-1]
      j--
    }
    arr[j] = temp
  }
}
function charuSort(A) {
  for (let i = 1; i < A.length; i++) {
    let p = A[i]
    let j = i
    while (j > 0 && p < A[j - 1]) {
      A[j] = A[j - 1]
      j--
    }
    A[j] = p
  }
}
// charuSort(A)

// 选择排序
// 在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
// 第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。
// 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。
function selectSort(arr) {
  for(let i = 0;i<arr.length; i++) {
    let index = i
    for(let j = i+1; j<arr.length; j++) {
      if(arr[j]<arr[index]) {
        index = j
      }
    }
    if(index != i){
      swap(arr, i, index)
    }
  } 
}
selectSort([3,5,2,4])
// 归并排序
// 排序逻辑
function merge(A, l, mid, r) {
  let B = A.slice(l, mid)
  let C = A.slice(mid, r)
  let k = 0
  let j = 0
  B.push(Number.POSITIVE_INFINITY)
  C.push(Number.POSITIVE_INFINITY)
  for(let i = l; i<r; i++) {
    A[i] = B[k] > C[j] ? C[j++] : B[k++]
  }
}
// 分
function merge_sort(A, l, r) {
  if(r-l < 2) return
  let mid = Math.floor((l+r)/2)
  merge_sort(A, l, mid)
  merge_sort(A, mid, r)
  merge(A, l, mid, r)
}


// r长度
// 
// let A = [7,5,4,3,2,1]
function merge(A, l, mid, r) {
  let B = A.slice(l, mid)
  let C = A.slice(mid, r)
  B.push(Number.POSITIVE_INFINITY)
  C.push(Number.POSITIVE_INFINITY)
  let k = 0
  let j = 0
  for (let i = l; i < r; i++) {
    // 相当于A是一个空数组 往里面塞数据
    A[i] = B[k] > C[j] ? C[j++] : B[k++]
  }
}

function merge_sort(A, l, r) {
  if (r - l < 2) return
  let mid = ~~((l + r) / 2)
  merge_sort(A, l, mid)
  merge_sort(A, mid, r)
  merge(A, l, mid, r)
}
// merge_sort(A, 0, 6)


// 快速排序
// 左右两边排序
function quick(A, l, r) {
  let prov = A[r-1]
  let j = l
  let k = r - 1
  while(j < k) {
    if(A[j] > prov) {
      swap(A, j, --k)
    }else{
      j++
    }
  }
  swap(A, k, r-1)
  return k
}
// 分
function quick_sort(A, l, r) {
  if(r-l<2) return
  let index = quick(A, l, r)
  quick_sort(A, l, index )
  quick_sort(A, index+1, r)
}


// 计数排序
// 找出最大的值  声明一个这么个长度的数组
// 把值插入这个数组   相邻的相加   然后再取出
function jishu(A) {
  let max = Math.max(...A)
  let B = Array(max + 1).fill(0)
  let C = []
  for (let i = 0; i < A.length; i++) {
    B[A[i]] += 1
  }
  // 
  for (let i = 0; i < B.length - 1; i++) {
    B[i + 1] = B[i + 1] + B[i]
  }
  // 取出来
  for (let i = 0; i < A.length; i++) {
    let p = B[A[i]]
    C[p - 1] = A[i]
    B[A[i]]--
  }
  console.log(C)
}
// jishu(A)
// console.log(A)